/*
 *  Copyright 2007-2008 by Matthias Buch-Kromann <mbk.isv@cbs.dk>.
 *  *
 *  This file is part of the Open-source Dependency Toolkit (OSDT),
 *  see http://code.google.com/p/open-source-dependency-toolkit.
 *  
 *  The OSDT is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as 
 *  published by the Free Software Foundation, either version 3 of 
 *  the License, or (at your option) any later version.
 * 
 *  The OSDT is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 * 
 *  You should have received a copy of the GNU Lesser General Public 
 *  License along with the OSDT in the files COPYING and COPYING.LESSER.
 *  If not, see http://www.gnu.org/licenses.
 */

package org.osdtsystem.graphs.views;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import org.osdtsystem.exceptions.EdgeNotFoundException;
import org.osdtsystem.exceptions.FeatureNotFoundException;
import org.osdtsystem.exceptions.IllegalCycleException;
import org.osdtsystem.exceptions.IllegalOrderException;
import org.osdtsystem.exceptions.NodeNotFoundException;
import org.osdtsystem.exceptions.NonUniqueNameException;
import org.osdtsystem.graphs.Graph;
import org.osdtsystem.values.EdgeID;
import org.osdtsystem.values.Feature;
import org.osdtsystem.values.Layer;
import org.osdtsystem.values.Location;
import org.osdtsystem.values.NodeID;
import java.util.List;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import org.osdtsystem.exceptions.IllegalRelationException;
import org.osdtsystem.exceptions.LocationNotFoundException;
import org.osdtsystem.exceptions.OsdtSyntaxException;
import org.osdtsystem.graphs.io.GraphIDs;

/**
 *
 * @author Matthias Buch-Kromann <mbk.isv@cbs.dk>
 */
public class DependencyTreeEngine implements DependencyTree {
    private final Tree tree;
    private Set<Object> adjunctRelations, complementRelations;
    
    
    /**
     * Add an unordered dependency tree with dependency edge relation labels to the given 
     * graph. <code>nodeCollection</code> is used as the underlying node collection,
     * and the node <code>top</code> is used as the formal top node of the dependency tree. 
     * The string <code>name</code> is used as the name of the layer used to store edges 
     * in the tree.
     * @param graph the graph used to store the tree
     * @param nodeCollection the collection of nodes in the tree
     * @param top the node used as the top node
     * @param name the name used for the new dependency tree layer
     * @throws NonUniqueNameException 
     */
    public DependencyTreeEngine(final Graph graph, final NodeCollection nodeCollection,
            final NodeID top, final String name) throws NonUniqueNameException {
        this(new TreeEngine(graph, nodeCollection, top, name + ViewConstants.TreeSuffix));
        graph.addView(this, name);
    }
    
    public DependencyTreeEngine(final Tree tree) {
        this.tree = tree;
        this.adjunctRelations = null;
        this.complementRelations = null;
    }

    @Override
    public View copy() {
        DependencyTree copy = new DependencyTreeEngine((Tree) tree.copy());
        copy.setAdjunctRelations(adjunctRelations);
        copy.setComplementRelations(complementRelations);
        return copy;
    }

    @Override
    public void addDependencyFeature(Feature feature) {
        tree.addEdgeFeature(feature);
    }

    @Override
    public void addNodeFeature(Feature feature) {
        tree.addNodeFeature(feature);
    }

    @Override
    public void setFeatureValue(Location location, Feature feature, Object value) 
            throws LocationNotFoundException, FeatureNotFoundException {
        tree.setFeatureValue(location, feature, value);
    }

    @Override
    public void setComplementRelations(final Set<Object> complementRelations) {
        this.complementRelations = complementRelations;
    }

    @Override
    public void setAdjunctRelations(final Set<Object> adjunctRelations) {
        this.adjunctRelations = adjunctRelations;
    }

    private boolean permissibleRelation(Object relation) {
        // Do not check when complement or adjunct relations haven't been specified
        if (adjunctRelations == null || complementRelations == null)
            return true;
        
        // If specified, check that relation is contained in positive-list
        return adjunctRelations.contains(relation)
                || complementRelations.contains(relation);
    }
    
    @Override
    public EdgeID setGovernor(NodeID node, NodeID governor, Object relation) 
            throws NodeNotFoundException, IllegalCycleException, IllegalRelationException, IllegalOrderException {
        // Check that relation is legal
        if (! permissibleRelation(relation))
            throw new IllegalRelationException("The given dependency relation " 
                    + relation + " is not on the list of permitted complement or adjunct" +
                    " relations");
        
        // Set parent in unordered tree
        return tree.setParent(node, governor, relation);
    }

    @Override
    public NodeID addNode(NodeID governor, Object relation) 
            throws NodeNotFoundException, IllegalRelationException, IllegalOrderException {
        // Check that relation is legal
        if (! permissibleRelation(relation))
            throw new IllegalRelationException("The given dependency relation " 
                    + relation + " is not on the list of permitted complement or adjunct" +
                    " relations");
        
        // Add node in unordered tree
        return tree.addNode(governor, relation);
    }

    @Override
    public void removeSubtree(NodeID node) {
        tree.removeSubtree(node);
    }

    @Override
    public NodeID top() {
        return tree.top();
    }

    @Override
    public List<EdgeID> dependencies() {
        return tree.edges();
    }

    @Override
    public List<NodeID> nodes() {
        return tree.nodes();
    }

    @Override
    public EdgeID governorEdge(NodeID node) {
        return tree.parentEdge(node);
    }

    @Override
    public List<EdgeID> dependentEdges(NodeID node) {
        return tree.childEdges(node);
    }

    @Override
    public List<EdgeID> complementEdges(NodeID node) {
        List<EdgeID> complementEdges = new ArrayList<EdgeID>();
        for (EdgeID dependency : dependentEdges(node))
            if (isComplement(dependency)) 
                complementEdges.add(dependency);
        return Arrays.asList(complementEdges.toArray(new EdgeID[0]));
    }

    @Override
    public List<EdgeID> adjunctEdges(NodeID node) {
        List<EdgeID> adjunctEdges = new ArrayList<EdgeID>();
        for (EdgeID dependency : dependentEdges(node))
            if (isAdjunct(dependency)) 
                adjunctEdges.add(dependency);
        return Arrays.asList(adjunctEdges.toArray(new EdgeID[0]));
    }

    @Override
    public boolean dominates(NodeID dominator, NodeID dominated) {
        return tree.dominates(dominator, dominated);
    }

    @Override
    public NodeID dependencyJoin(NodeID node1, NodeID node2) 
            throws NodeNotFoundException {
        return tree.join(node1, node2);
    }

    @Override
    public List<List<EdgeID>> dependencyJoinPaths(NodeID node1, NodeID node2) 
            throws NodeNotFoundException {
        return tree.joinPaths(node1, node2);
    }

    @Override
    public int height(NodeID node) throws NodeNotFoundException {
        return tree.height(node);
    }

    @Override
    public NodeID governor(EdgeID edge) {
        return tree.parent(edge);
    }

    @Override
    public NodeID dependent(EdgeID edge) {
        return tree.child(edge);
    }

    @Override
    public Object relation(EdgeID edge) throws EdgeNotFoundException {
        return tree.relation(edge);
    }

    @Override
    public boolean isComplement(EdgeID edge) {
        try {
            if (complementRelations != null) {
                return complementRelations.contains(relation(edge));
            } else {
                // True if complement relations undefined and edge is 
                // defined as a non-adjunct
                return (adjunctRelations != null)
                        ? ! adjunctRelations.contains(relation(edge))
                        : false;
            }
        } catch (EdgeNotFoundException ex) {
            return false;
        }
    }

    @Override
    public boolean isAdjunct(EdgeID edge) {
        try {
            if (adjunctRelations != null) {
                return adjunctRelations.contains(relation(edge));
            } else {
                // True if adjunct relations undefined and edge is 
                // defined as a non-complement
                return (complementRelations != null)
                        ? ! complementRelations.contains(relation(edge))
                        : false;
            }
        } catch (EdgeNotFoundException ex) {
            return false;
        }
    }

    @Override
    public List<Feature> nodeFeatures() {
        return tree.nodeFeatures();
    }

    @Override
    public List<Feature> edgeFeatures() {
        return tree.edgeFeatures();
    }

    @Override
    public Object featureValue(Location location, Feature feature) {
        return tree.featureValue(location, feature);
    }

    @Override
    public void setGraph(Graph graph) {
        tree.setGraph(graph);
    }

    @Override
    public void clear() {
        tree.clear();
    }
    
    @Override
    public boolean containsNode(NodeID node) {
        return tree.containsNode(node);
    }

    // 1=view ID, 3=node collection, 5=top node, 7=tree layer
    private static final Pattern osdtDependencyTreeEnginePattern = Pattern.compile(
            "^\\s*VIEW([0-9]+)\\s+DependencyTreeEngine\\((VIEW)?([0-9]+)\\)\\s*$");
    

    @Override
    public String toOSDT(Graph graph, GraphIDs ids) {
        return "DependencyTreeEngine(VIEW" + ids.id(tree) + ")";
    }

    public static DependencyTreeEngine fromOSDT(Graph graph, GraphIDs ids, String osdt)
            throws OsdtSyntaxException {
        // Parse OSDT string
        Matcher m = osdtDependencyTreeEnginePattern.matcher(osdt);
        if (! m.find())
            return null;
        
        // Find source and target node collections, and alignment layer
        try {
            // Find view ID, node collection, top node, and tree layer
            int viewID = Integer.parseInt(m.group(1));
            TreeEngine treeEngine = (TreeEngine) ids.getView(Integer.parseInt(m.group(3)));
            
            // Create new tree engine
            return new DependencyTreeEngine(treeEngine);
        } catch (Exception ex) {
            throw new OsdtSyntaxException("Cannot find view or layer in OSDT string: " + osdt);
        }
    }

    @Override
    public void recompute() {
        // TODO
        // throw new UnsupportedOperationException("Not yet implemented");
    }

    @Override
    public List<NodeID> adjuncts(NodeID node) {
        return edges2dependents(adjunctEdges(node));
    }

    @Override
    public List<NodeID> complements(NodeID node) {
        return edges2dependents(complementEdges(node));
    }

    @Override
    public List<NodeID> dependents(NodeID node) {
        return edges2dependents(dependentEdges(node));
    }

    @Override
    public NodeID governor(NodeID node) {
        return governor(governorEdge(node));
    }

    private List<NodeID> edges2dependents(List<EdgeID> edges) {
        Set<NodeID> nodes = new HashSet<NodeID>(edges.size());
        for (EdgeID edge : edges) {
            nodes.add(dependent(edge));
        }
        return Arrays.asList(nodes.toArray(new NodeID[0]));
    }

    @Override
    public void addEdgeFeature(Feature feature) {
        addDependencyFeature(feature);
    }

    @Override
    public EdgeID setParent(NodeID child, NodeID parent, Object relation) 
            throws NodeNotFoundException, IllegalCycleException, IllegalOrderException, 
            IllegalRelationException {
        return setGovernor(parent, parent, relation);
    }

    @Override
    public List<EdgeID> edges() {
        return dependencies();
    }

    @Override
    public EdgeID parentEdge(NodeID node) {
        return governorEdge(node);
    }

    @Override
    public List<EdgeID> childEdges(NodeID node) {
        return dependentEdges(node);
    }

    @Override
    public NodeID join(NodeID node1, NodeID node2) throws NodeNotFoundException {
        return dependencyJoin(node1, node2);
    }

    @Override
    public List<List<EdgeID>> joinPaths(NodeID node1, NodeID node2) throws NodeNotFoundException {
        return dependencyJoinPaths(node1, node2);
    }

    @Override
    public NodeID parent(EdgeID edge) {
        return governor(edge);
    }

    @Override
    public NodeID child(EdgeID edge) {
        return dependent(edge);
    }

    @Override
    public Layer treeLayer() {
        return tree.treeLayer();
    }
}
